package special;

import java.util.Arrays;
import java.util.Random;

public class GuiBingSort {
    public static void main(String[] args) {
        int[] nums = new int[10000];
        Random r = new Random();
        for (int i = 0; i < 10000; i++) {
            nums[i] = r.nextInt(10000);
        }
        guiBingSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
    private static int[] guiBingSort(int[] arr, int l, int r){
        if (l == r){
            return arr;
        }
        if (r - l == 1){
            if (arr[l] > arr[r]){
                int tmp = arr[l];
                arr[l] = arr[r];
                arr[r] = tmp;
            }
            return arr;
        }
        int m = l + (r - l) / 2;
        guiBingSort(arr, l, m);
        guiBingSort(arr, m + 1, r);
        int[] copy = Arrays.copyOf(arr, arr.length);
        int il = l, ir = m + 1, i = l;
        while (il <= m && ir <= r){
            if (copy[il] > copy[ir]){
                arr[i] = copy[ir];
                ir++;
                i++;
            }else {
                arr[i] = copy[il];
                il++;
                i++;
            }
        }
        if (il > m){
            for (int j = ir; j <= r; j++, i++) arr[i] = copy[j];
        }else {
            for (int j = il; j <= m; j++, i++) arr[i] = copy[j];
        }
        return arr;
    }
}
